package oj;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC15 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        for(int i=0;i<n;i++){
            if(nums[i]>0) return res;
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int j=i+1;
            int k=n-1;

            while(j<k){
                int sum=nums[i]+nums[j]+nums[k];
                if(sum==0){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    res.add(list);
                }
                if(sum>0){
                    int k0=k-1;
                    while(j<k0 && nums[k]==nums[k0]){
                        k0--;
                    }
                    k=k0;
                }else{
                    int j0=j+1;
                    while(j0<k && nums[j]==nums[j0]){
                        j0++;
                    }
                    j=j0;
                }
            }

        }
        return res;
    }
}
